package cn.edu.zzuli.sort;

import java.util.Arrays;

public class ShellSort {


    public static void main(String[] args) {
        //希尔排序，本质上也是一种插入排序，只不过进行了分组，每次都利用前一次排好序的数据，交换次数更少。
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};

        //多少个一组，现在有10个数，第一次 分成5组，第二次分成2组，最后分为1组也就是排好序的值
        for (int gap = arr.length / 2; gap > 0; gap = gap / 2) {

            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[i];
                //当 j-gap 位置的数 比 j大的时候才开始插入排序
                if (arr[j - gap] > temp) {
                    //找到要插入的位置，并且在插入的过程中后移。
                    while (j - gap >= 0 && arr[j - gap] > temp) {
                        //数据整体向后移
                        arr[j] = arr[j - gap];
                        //继续向前遍历
                        j = j -gap;
                    }
                    //到这里时，已经找到了最小值的位置,直接插入。
                    arr[j] = temp;
                    System.out.println("gap = " + gap + ", arr的情况~:" +Arrays.toString(arr));
                }
            }
        }

    }

}
